package com.jeff.huawei.practice;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 题目描述
 * 近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。
 * <p>
 * 一个月后，有M棵胡杨未能成活。
 * <p>
 * 现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
 * <p>
 * 输入描述
 * N 总种植数量，1 <= N <= 100000
 * <p>
 * M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列，1 <= M <= N
 * <p>
 * K 最多可以补种的数量，0 <= K <= M
 * <p>
 * 输出描述
 * 最多的连续胡杨棵树
 */
public class Third1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //读取原先种植了多少棵胡杨
        int N = scanner.nextInt();
        //读取未成活的胡杨数
        int M = scanner.nextInt();

        //初始化一个数组,数组的0索引对应着第一棵胡杨,1索引对应着第二棵胡杨,以此类推,数组初始化为1,表示所有胡杨都成活
        int[] nums = new int[N];
        Arrays.fill(nums, 1);


        //读取未成活的胡杨的编号,并将其标记为0
        for (int i = 0; i < M; i++) {
            int num = scanner.nextInt();
            nums[num - 1] = 0;
        }
        //读取可以补种的树
        int K = scanner.nextInt();

        //初始化滑动窗口的左右边界
        int left = 0;
        int right;
        int maxLen = 0;


        //遍历所有胡杨,使用滑动窗口的思路,确定最长的连续活胡杨数
        for (right = 0; right < nums.length; right++) {

            int count = count(nums, left, right);
            if (count > K) {
                //如果当前窗口内的0的数量大于K,则将左边界向右移动一位,直到窗口内的0的数量小于等于K
                while (count > K) {
                    //左边界向右移动一位 判断左边界是否为0,如果是0,则数量减一
                    if (nums[left] == 0) {
                        count--;
                    }
                    left++;
                }
            }
            maxLen = Math.max(maxLen, right - left+1);
        }
        System.out.println(maxLen);
    }

    //想办法计算左右边界之内的补种的树木的数量
    private static int count(int[] nums, int left, int right) {
       //统计left和right之间的0的数量
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == 0) {
                count++;
            }
        }
        return count;
    }


}

